package main

import (
	"fmt"
	"math"
)

func main() {
	fmt.Println(divide(10, 3))
}

//给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
//
// 返回被除数 dividend 除以除数 divisor 得到的商。
//
// 整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
//
//
//
// 示例 1:
//
// 输入: dividend = 10, divisor = 3
//输出: 3
//解释: 10/3 = truncate(3.33333..) = truncate(3) = 3
//
// 示例 2:
//
// 输入: dividend = 7, divisor = -3
//输出: -2
//解释: 7/-3 = truncate(-2.33333..) = -2
//
//
//
// 提示：
//
//
// 被除数和除数均为 32 位有符号整数。
// 除数不为 0。
// 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231 − 1。本题中，如果除法结果溢出，则返回 231 − 1。
//
// Related Topics 数学 二分查找
// 👍 492 👎 0

//leetcode submit region begin(Prohibit modification and deletion)
func divide(dividend, divisor int) int {
	// 什么情况下会溢出呢？
	// 因为环境只能存储 32 位有符号整数，所以dividend、divisor肯定不会溢出，
	// 当dividend = minInt32, divisor = -1时，结果是2^31溢出了
	// 当divisor是1的时候，结果就是dividend
	// 当dividend是0时，结果就是0
	if dividend == 0 {
		return 0
	}
	if divisor == 1 {
		return dividend
	}
	if divisor == -1 && dividend == math.MinInt32 {
		return math.MaxInt32
	}
	// 都取负数，因为负数的空间更大，正数有可能溢出
	var sign bool
	if (dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0) {
		sign = true
	}
	if dividend > 0 {
		dividend = 0 - dividend
	}

	if divisor > 0 {
		divisor = 0 - divisor
	}
	// 接下来就可以按照计算器的2进制除法来实现了
	result := div(dividend, divisor)
	if sign {
		result = 0 - result
	}
	return result
}

func div(a, b int) int {
	if a > b {
		return 0
	}
	var count int
	count = 1
	tmpB := b
	// tmpB+tmpB可能会溢出，溢出会变成非负数
	for tmpB+tmpB >= a && tmpB+tmpB < 0 {
		count = count + count
		tmpB = tmpB + tmpB
	}
	return count + div(a-tmpB, b)
}

//leetcode submit region end(Prohibit modification and deletion)
